package C052;

import java.util.Arrays;

/**
 * ClassName: C05
 * Package: C052
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/3/28 18:09
 * @Version 1.0
 * @Since 1.0
 */
public class C05 {
    public static void main(String[] args) {
//        char[][] arr = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};

        char[][] arr = {{'0', '0', '1', '0' }, {'0', '0', '1', '0' }, {'0', '0', '1', '0' }, {'0', '0', '1', '1' }, {'0', '1', '1', '1' }, {'0', '1', '1', '1' }, {'1', '1', '1', '1' }};
        System.out.println(maximalRectangle(arr));
    }

    static int n, m, MAXLEN = 200;
    static int[] arr = new int[MAXLEN];

    public static int maximalRectangle(char[][] matrix) {
        // 遍历每一行，在每一行的基础上进行单调栈的求解即可
        n = matrix.length;
        m = matrix[0].length;
        int ans = 0;
        Arrays.fill(arr, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {
                    arr[j]++;
                } else {
                    arr[j] = 0;
                }
            }
            ans = Math.max(ans, largestArea());
        }
        return ans;
    }

    // 求最大的面积
    static int[] stack = new int[MAXLEN];
    static int r, pop, left;

    private static int largestArea() {
        r = 0;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            while (r > 0 && arr[stack[r - 1]] >= arr[i]) {
                pop = stack[--r];
                left = r == 0 ? -1 : stack[r - 1];
                ans = Math.max(ans, arr[pop] * (i - left - 1));
            }
            stack[r++] = i;
        }
        // 处理剩余的元素
        while (r > 0) {
            pop = stack[--r];
            left = r == 0 ? -1 : stack[r - 1];
            ans = Math.max(ans, arr[pop] * (m - left - 1));
        }
        return ans;
    }
}
